Various researches have been made of algorithms for detecting a plane from three-dimensional distance data. A plane thus detected can be used to have a locomotion robot apparatus, for example, bypass an obstacle or climb stairs.
Generally, a plane is detected from distance information in the following steps:
1. Three-dimensional distance information is acquired.
2. The information is segmented for a plurality of planes.
3. For each of the plane segments, the center of gravity, plane equation, boundary, etc. are calculated.
4. The steps 2 and 3 are repeated to acquire an optimum method of segmentation.
For example, an image of stairs placed on a floor surface as shown in FIG. 1A is segmented into four planar regions A, B, C and D as shown in FIG. 1B. The region A indicates the floor part, and regions B, C and D show the stair parts.
Next, there will be briefly described the conventional techniques for detecting a plane from three-dimensional distance information, as disclosed in the following non-patent documents:                No. 1: A. Hoover, G. Jean-Baptiste, X. Jiang, P. J. Flynn, H. Bunke, D, Goldgof, K. Bowyer, D. Eggert, A. Fitsgibbon and R. Fisher, “An Experimental Comparison of Range Image Segmentation Algorithms”, Transaction on Pattern Analysis Machine Intelligence, 18(7), 1996        No. 2: L. Iocchi, K. Konolige and M. Bajracharya, “Visually Realistic Mapping of Planar Environment with Stereo”, Int. Symposium on Experimental Robotics (ISER), 2000        No. 3: K. Okada, S. Kagami, M. Inaba and H. Inoue, “Plane Segment Finder: Algorithm, Implementation, and Applications”, Int. Conf. on Robotics and Automation (ICRA), 2001        No. 4: X. -Y. Jiang and H. Bunke, “Fast Segmentation of Range Images into Planar Regions by Scan Line Grouping”, Machine Vision and Applications, 7(2), p 115, 122, 1994.        
In the document No. 1, it is proposed to sample a reference point at random from distance information and detect a plane by connecting the reference point to points spatially near the reference point. In the document No. 2, it is proposed to detect a plane statistically from distance information by the Hough transformation. In the document No. 3, it is proposed to fit three points selected at random from distance information to the plane equation and detect a plane statistically by the randomized Hough transformation. In the document No. 4, it is proposed to use the scan line grouping method on the basis of the fact that a group of points in line in a range image will form a straight line in a space when the points are in one plane in a three-dimensional space.
Note that the plane detection using the distance information as disclosed in the above-mentioned non-patent document Nos. 1 to 4 incur important problems of “under-segmentation” and “over-segmentation” caused by noises.
The “under-segmentation” is such that a plurality of planes, actually existing, is recognized as one plane which will be resulted from averaging of them, for example, under the influence of noises. The “over-segmentation” is such that a single plane is recognized as a plurality of different planes under the influence of noises.
A range image captured by cameras 401R and 401L, as shown in FIG. 2, includes a plurality of treads, lateral surface and floor surface. In case there are stairs 400 in the field of view of the cameras 401R and 401L, for example, as shown in the upper portion of FIG. 2, a plurality of planes is included in the range image. Therefore, an x-z plane includes a plurality of planes such as treads 402, lateral surfaces 403, etc. as shown in the lower portion of FIG. 2. However, the under-segmentation will cause the plurality of planes to be detected as one plane 403 without distinction of the plurality of planes. Generally, the plane detection unit detects planes from measured data more influenced by noises than the required accuracy of plane detection. The plane detection unit has to be designed with a smaller threshold for breaking a plane into a plurality of plane segments, which will unavoidably lead to such an under-segmentation. On the contrary, reduction of the threshold for measured data much influenced by noises will lead to the over-segmentation, namely, segmentation of a plane into a plurality of planes.
In case a plane is estimated by the Hough transformation as in the aforementioned non-patent document Nos. 1 and 2, the under-segmentation will take place with a high possibility. FIGS. 3A to 3D explain the extraction of a plane by the Hough transformation. FIG. 3A shows stairs, FIG. 3B shows three-dimensional distance data acquired form the stairs in FIG. 3A, FIG. 3C shows peaks detected by the Hough transformation of the distance data in FIG. 3B, and FIG. 3D shows the result of comparison between a plane defined by the peaks in FIG. 3C and actual plane. When the stairs 410 are covered by the field of view as shown in FIG. 3, the three-dimensional data of the stairs will be as shown in FIG. 3B. Three points of this data are selected at random to determine a plane and the plane is placed in a plane parameter space to plot a histogram. Thus, a dominant plane can be determined as a peak P as shown in FIG. 3C, and a plane depending upon parameters indicated by the peak P is estimated to fall in the field of view.
However, when a plane is statistically estimated from data having subjected to the Hough transformation, the under-segmentation will result in a value which is statistically most dominant one. That is, the detected plane 411 will be determined as a plane which is a result of averaging all planes 412, 413 and 414, as shown in FIG. 3D. Namely, the Hough transformation permits to estimate and detect a dominant plane in the field of view, but not to detect a plurality of planes, if any, with a high accuracy.
The above-mentioned non-patent document No. 4 discloses a plane extraction method using the scan line grouping. In the plane detection by the scan line grouping, three-dimensional distance data is first acquired from a captured image, and processed as follows per line- or column-directional data train (image row). For example, a train of line-directional data in an image, which are in one plane in a three-dimensional space is in one line, which is utilized to generate line segments (will be referred to as “line” hereunder wherever appropriate) from a group of data points in one plane. Then, three adjacent lines in one plane are extracted from the generated group of lines to determine a reference plane. In case lines adjacent to the reference plane are in one plane, the region of the reference plane is grown by the adjacent lines and the reference plane is updated, whereby a plane is detected.
FIG. 4 shows a flow of operations made in the plane detection by the scan line grouping. As shown in FIG. 4, a range image (in step S41) is first supplied to generate lines from a group of data points estimated to be in one plane in each line- or column-directional data train forming the range image (in step S42). The generated line group is searched for a region which will be the seed of a plane (will be referred to as “seed region” hereunder) and selects the seed region (in steps S43 and 44). For this selection, vertically adjacent lines should be in one plane. A plane to which the seed region defined by the selected three lines is determined by averaging the three lines.
It is checked in the data train adjacent to the seed region selected in step S3 whether there are lines in a plane coplanar to the seed region. It is judged through a spatial comparison whether such lines are in one plane. In case there exist lines determined to be in one plane, the lines are added to the seed region (region growing) and the original plane including the added lines is updated (plane updating). These operations are repeatedly done to grow the region and update the plane (in step S45). Further, the operations in steps S43 to S45 are done repeatedly until no regions to be the seed are found. Finally, ones of a plurality of regions in a group thus determined, which form together one plane, are coupled to each other (in step S46) and the process is ended.
Each of the operations shown in FIG. 4 will be described in further detail below. Firstly, the line fitting in step S42 will be explained. FIG. 5 explains the conventional line fitting, in which FIGS. 5A to 5C show the steps of line fitting, respectively. First, a line (string) 431 connecting both ends 430a and 430b of a given group of data points 430 is generated as shown in FIG. 5A. Then, the data point group is searched for a data point whose distance to the generated line 431 is largest. In case the distance d between a data point 430c thus searched and line 431 exceeds a threshold, the line 431 is segmented. More specifically, the line 431 is segmented into a line 431a connecting the left end point 430a and data point 430c which is a break point, and a line 431b connecting the break point 430c and right end point 430b as shown in FIG. 5B. The segmentation is repeatedly done until the distance between all these points and lines becomes smaller than a threshold, whereby a plurality of lines fit to given data can be extracted. In this embodiment, the data points 430c and 430d which are finally break points at two places are selected as shown in FIG. 5C, and the line 431 is segmented into three lines 431a, 431c and 431d. 
FIG. 25 explains the region growing done in step S45. A region can be segmented by sequentially merging the lines resulted from the aforementioned line fitting starting with the seed region. For example, in case there is a plurality of stairs 31 in an image 30 as shown in FIG. 25, it is assumed that there is selected a seed region defined by three lines 32a to 32c indicated each with a thick line, for example. In this case, these three lines 32a to 32c define together a seed region. First, one plane (reference plane) P defined by the three lines 32a to 32c is determined. Next, in a data train 33 or 34 adjacent, outside the seed region, to the line 32a or 32c at the outermost side of the seed region, lines coplanar with the plane P are selected. In this embodiment, the line 33a is selected. Then, a plane P′ defined by the group of four lines is determined to update the reference plane P. Next, when the line 34a is selected, a plane P″ defined by a group of five lines is determined to update the plane P′. By repeating these operations, the second tread of the stairs 31 can be determined as a plane 45 indicated with a dash line. The region growing operation is done in this way until there exist no additional lines for growing the selected seed region. When there are no additional lines, the image 30 is searched again for three lines which will define a seed region in order to make the region growing. These operations are repeatedly done. The operations in steps S43 to S45 in FIG. 4 are repeated until no further three lines for a seed region exist.
With the plane detection algorithm using the scan line grouping, however, it is extremely difficult to determine a threshold for the line fitting. Therefore, it is very difficult to exclude the influence of noises in the measured data. FIG. 6 shows results of the line fitting made with two different thresholds, respectively. FIGS. 6A shows the result of the line fitting operation made with one threshold set for a group of measured data points 450 with less noises, and 6B shows the result of the line fitting operation made with another threshold set for a group of measured data points 460 with many noises. The threshold for the line fitting as shown in FIG. 6A is a large one, while that for the line fitting as shown in FIG. 6B is a small one.
As shown in FIG. 6A, the large threshold set for line fitting of the group of measured data points 450 with less noises results in under-segmentation. For this line fitting, a small threshold will provide better results of line fitting. On the other hand, setting of a small threshold for line fitting of the group of measured data points 460 with many noises results in over-segmentation as shown in FIG. 6B For this line fitting, a large threshold has to be set. That is to say, with a small threshold, a line will be segmented excessively small under the influence of noises, and it is not possible to extract lines which could normally be extracted.
Generally, data acquired by the distance measuring unit (range finder) such as stereo vision system from a near point is highly accurate and have less noises, but data acquired from a far point is low in accuracy and has many noises. Therefore, it is desirable to set a threshold adaptively to a distance between the range finer and object point. However, since the variation in measuring accuracy due to the environment will have an influence on the data acquisition, it is difficult to set a unique threshold for such a data acquisition.
In effect, the plane detection based on the randomized Hough transformation is suitable for use to detect a dominant plane, but when applied for detection of a plurality of planes from data including a plurality of planes such as stairs, it will cause the under-segmentation problem. Also, when the scan line grouping is used to extract planes, it is difficult to set a threshold for the line fitting. Use of the scan line grouping will cause the over-segmentation and under-segmentation problems. Both the randomized Hough transformation and scan line grouping are not advantageous in that it is difficult to detect planes accurately from measured distance data.